package formal.linkedList;

import java.util.Stack;

/**
 * 两数相加
 *
 * @author DengYuan2
 * @create 2021-01-08 20:06
 */
public class M_445 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
//        ListNode n2 = new ListNode(6);
//        ListNode n3 = new ListNode(5);
//        n1.next = n2;
//        n2.next = n3;
        ListNode m1 = new ListNode(9);
//        ListNode m2 = new ListNode(9);
//        ListNode m3 = new ListNode(4);
//        ListNode m4 = new ListNode(5);
//        m1.next = m2;
//        m2.next = m3;
//        m3.next = m4;
        ListNode listNode = addTwoNumbers(n1, m1);
        System.out.println(listNode);
    }

    /**
     * 我的写法-栈
     *
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        ListNode h1 = l1;
        ListNode h2 = l2;
        int a = 0;
        int b = 0;
        ListNode nNode = new ListNode(-1);
        while (h1 != null) {
            stack1.push(h1);
            h1 = h1.next;
        }
        while (h2 != null) {
            stack2.push(h2);
            h2 = h2.next;
        }
//        while (!stack1.isEmpty() || !stack2.isEmpty()) {
//            int first = stack1.isEmpty() ? 0 : stack1.pop().val;
//            int second = stack2.isEmpty() ? 0 : stack2.pop().val;
//            a = (first + second + b) % 10;
//            b = (first + second + b) / 10;
//            ListNode listNode = new ListNode(a);
//            listNode.next = nNode.next;
//            nNode.next = listNode;
//        }
//        // 注意b的值！！！
//        if (b != 0) {
//            ListNode listNode = new ListNode(1);
//            listNode.next = nNode.next;
//            nNode.next = listNode;
//        }

        //根据官方，可以将我上面的放到一起啊
        while (!stack1.isEmpty() || !stack2.isEmpty() || b!=0) {
            int first = stack1.isEmpty() ? 0 : stack1.pop().val;
            int second = stack2.isEmpty() ? 0 : stack2.pop().val;
            a = (first + second + b) % 10;
            b = (first + second + b) / 10;
            ListNode listNode = new ListNode(a);
            listNode.next = nNode.next;
            nNode.next = listNode;
        }
        return nNode.next;
    }
}
